We prove $n^{1+\Omega(1/p)}/p^{O(1)}$ lower bounds for the space complexityof $p$-pass streaming algorithms solving the following problems on $n$-vertexgraphs: * testing if an undirected graph has a perfect matching (this implies lowerbounds for computing a maximum matching or even just the maximum matchingsize), * testing if two specific vertices are at distance at most $2(p+1)$ in anundirected graph, * testing if there is a directed path from $s$ to $t$ for two specificvertices $s$ and $t$ in a directed graph. Prior to our result, it was known that these problems require $\Omega(n^2)$space in one pass, but no $n^{1+\Omega(1)}$ lower bound was known for any $p\ge2$. These streaming results follow from a communication complexity lower boundfor a communication game in which the players hold two graphs on the same setof vertices. The task of the players is to find out whether the sets ofvertices at distance exactly $p+1$ from a specific vertex intersect. The gamerequires a significant amount of communication only if the players are forcedto speak in a specific difficult order. This is reminiscent of lower bounds forcommunication problems such as indexing and pointer chasing. Among otherthings, our line of attack requires proving an information cost lower bound fora decision version of the classic pointer chasing problem and a direct sum typetheorem for the disjunction of several instances of this problem.
展开▼
机译：我们证明$ n ^ {1+ \ Omega（1 / p）} / p ^ {O（1）} $的下界是$ p $ -pass流算法的空间复杂度，可解决$ n $ -vertexgraphs上的以下问题： *测试无向图是否具有完美匹配（这意味着计算最大匹配甚至更低的最大匹配大小的下限），*测试两个特定顶点在无向图中的距离是否最大为$ 2（p + 1）$，*测试在有向图中两个特定顶点$ s $和$ t $是否存在从$ s $到$ t $的有向路径。在得出结果之前，我们已经知道这些问题需要通过一次$ \ Omega（n ^ 2）$空间，但是对于任何$ p \都没有$ n ^ {1+ \ Omega（1）} $下界ge2 $。这些流式传输结果来自于通信游戏的通信复杂度下限，在通信游戏中，玩家在同一组顶点上持有两个图形。玩家的任务是找出与特定顶点的距离恰好为$ p + 1 $的顶点集是否相交。仅当玩家被迫以特定的困难顺序讲话时，游戏才需要大量的交流。这使人联想到索引和指针追逐等通信问题的下限。除其他外，我们的攻击路线要求证明经典指针追逐问题的决策版本的信息成本下限，以及证明该问题的多个实例不成立的直接和类型定理。
展开▼
